package heap.heapSort;

/**
 * 优化的堆排序，构建堆的时间不需要额外的空间，直接原地进行排序
 * mxf
 * 2018年6月5日09:35:14
 */
public class HeapSort {

    public static void sort(Comparable[] arr) {
        int n = arr.length;
        // 注意，此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始
        // 最后一个元素的索引 = n-1

        for(int i = (n - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(arr, n, i);
        }

        for(int i = n - 1; i > 0; i--) {
            swap(arr, i, 0);
            shiftDown(arr, i, 0);
        }
    }

    private static void shiftDown(Comparable[] arr, int n, int k) {
        Comparable v = arr[k];
        while(2 * k + 1 < n) {
            int j = 2 * k + 1;
            if(j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
                j = j + 1;
            }
            if(v.compareTo(arr[j]) > 0) {
                break;
            }
            arr[k] = arr[j];
            k = j;
        }
        arr[k] = v;
    }

    private static void swap(Comparable[] arr, int i, int j) {
        Comparable v = arr[i];
        arr[i] = arr[j];
        arr[j] = v;
    }

    // 测试 HeapSort
    public static void main(String[] args) {

        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100);
        HeapSort.sort(arr);
        SortTestHelper.printArray(arr);
        return;
    }

}
